package com.leetcode.weekly.contest.no285th;

/**
 * @author 覃国强
 * @date 2022-03-20 11:06
 */
public class A03_射箭比赛中的最大得分 {

  static
  class Solution {
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
      int[] bobArrows = new int[aliceArrows.length];
      return maxBobPoints(numArrows, aliceArrows, 0, bobArrows);
    }

    private int[] maxBobPoints(int numArrows, int[] aliceArrows, int index, int[] bobArrows) {

      if (index == bobArrows.length) {
        int[] result = new int[bobArrows.length];
        System.arraycopy(bobArrows, 0, result, 0, bobArrows.length);
        result[0] += numArrows;
        return result;
      }

      // 不要当前的靶位
      int[] bobArrows1 = maxBobPoints(numArrows, aliceArrows, index + 1, bobArrows);
      int arrows1 = getArrows(bobArrows1, aliceArrows);

      // 要当前靶位
      if (numArrows > aliceArrows[index]) {
        bobArrows[index] = aliceArrows[index] + 1;
        numArrows -= (aliceArrows[index] + 1);
        int[] bobArrows2 = maxBobPoints(numArrows, aliceArrows, index + 1, bobArrows);
        int arrows2 = getArrows(bobArrows2, aliceArrows);
        bobArrows[index] = 0;

        return arrows2 > arrows1 ? bobArrows2 : bobArrows1;
      }

      return bobArrows1;
    }

    private int getArrows(int[] bobArrows, int[] aliceArrows) {
      int arrow = 0;
      for (int i = 0; i < bobArrows.length; ++i) {
        if (bobArrows[i] > aliceArrows[i]) {
          arrow += i;
        }
      }
      return arrow;
    }
  }

}
